import java.util.Arrays;
import java.util.HashSet;

public class Main1 {
    public static void main(String[] args) {
//        String str1 = "";
////        String str2 = "a";
////        String str3 = "abcba";
////        String str4= "gtbhg";
////        System.out.println(isPlainString(str1));

//        String str = "babad";
//        System.out.println(theLongestPlainString(str));

        String s1 = "A man, a plan, a canal: Panama";
        String s2 = "race a car";
        String s3 = "abcbxa";
        String s4 = "bcabcbb";
//
//        System.out.println(lengthOfLongestSubstring(s4));

        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] res = maxSlidingWindow(nums,k);
        System.out.println(Arrays.toString(res));

    }

    // 判断字符串是否是回文字符串
    // 双指针法
    public static boolean isPlainString1(String str){
        if(str == null || str.length() == 0) return true;

        int i = 0;
        int j = str.length()-1;

        // 从首尾往中间走
        while (i < j){
            if(str.charAt(i) != str.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    // 最长回文字符串
    // 中心扩展法
    public static String theLongestPlainString(String str){
        if(str.length() == 0) return str;
        int maxLength = 1;   // 记录回文字符串的长度
        int ll = 0;   // 记录最长回文串的起始位置
        int rr = 0;   // 记录最长回文串的终止位置

        for (int i = 0; i < str.length()-1; i++) {

            // 首先以i为中心
            int l = i-1;
            int r = i+1;
            while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r)){
                int len = r - l + 1;
                if(len > maxLength){
                    maxLength = len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }

            // 情况2，以i和i+1为中心
            l = i;
            r = i+1;
            while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r)){
                int len = r - l + 1;
                if(len > maxLength){
                    maxLength = len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }
        }
        return str.substring(ll,rr+1);
    }

    // 判断回文字符串，只考虑字符和数字,可以忽略字母的大小写。
    public static boolean isPlainString2(String str){

        if(str == null || str.length() == 0) return true;

        int i = 0;
        int j = str.length()-1;
        while (i < j){

            // 1、判断位置i处是否是数字或字母字符
            while (!Character.isLetterOrDigit(str.charAt(i))){
                i++;
            }
            // 2、判断位置j处是否是数字或字母字符
            while (!Character.isLetterOrDigit(str.charAt(j))){
                j--;
            }
            // 3、可以忽略大小写
            if(Character.toLowerCase(str.charAt(i)) != Character.toLowerCase(str.charAt(j))){
                return false;
            }
            i++;
            j--;

        }
        return true;
    }

    /**
     * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
     *
     * 输入: "aba"
     * 输出: True
     *
     * 输入: "abca"
     * 输出: True
     * 解释: 你可以删除c字符。
     */
    public static boolean isPlainString3(String str){
        if(str==null || str.length() == 0) return true;

        int i = 0;
        int j = str.length()-1;

        while (i < j){
            if(str.charAt(i) == str.charAt(j)){
                i++;
                j--;
            }else
                // 不相等再给一次机会
                // abcbxa --> bcbx --> bcb || cbx
                return isStrictPlainString(str,i+1,j)||isStrictPlainString(str,i,j-1);
        }
        return true;
    }


    // 判断字符串i到j位置是否是严格的回文字符串
    public static boolean isStrictPlainString(String s,int i,int j){
        while (i < j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    /**
     * 无重复的最长子串
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     */
    public static int lengthOfLongestSubstring(String s){
        if(s == null || s.length() == 0) return 0;

        HashSet<Character> set = new HashSet<>();

        int res = 0;
        int left = 0;
        int right = 0;

        while (left < s.length() && right < s.length()){

            if(!set.contains(s.charAt(right))){
                set.add(s.charAt(right));
                right++;
                res = Math.max(res,right-left);
            }else{
                set.remove(s.charAt(left));
                left++;
            }
        }
        return res;
    }

    // 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) return new int[0];

        int[] res = new int[nums.length-k+1];

        int left = 0;
        int right = k-1;

        while (right < nums.length){
            int max = getMax(nums,left,right);
            res[left] = max;
            left++;
            right++;
        }
        return res;
    }

    // 获取窗口内的最大值
    private static int getMax(int[] nums, int left, int right) {
        int max = nums[left];

        for (int i = left; i <= right ; i++) {
            if(max < nums[i]){
                max =  nums[i];
            }
        }
        return max;
    }

}
